In multiprocessor computer systems, software programs may be executed by threads that are run in parallel on the processors that form the multiprocessor computer system. As a result, a program may be run in parallel on different processors since concurrently running threads may be executing the program simultaneously. Moreover, if a program can be broken down into constituent processes, such computer systems can run the program very quickly since concurrently running threads may execute in parallel the constituent processes. Single processor, multitasking computer systems can also execute multiple threads of execution virtually simultaneously through the use of various resource scheduling mechanisms well known to those skilled in the art of multitasking operating system design.
The programs running on such computer systems may be object-oriented. In other words, the threads executing the programs may invoke methods of objects to perform particular functions. However, because of software and/or hardware constraints in the computer system, only a predefined number of objects may be allowed to implement functions at one time. For example, an object may require access to a shared computer resource, such as an I/O device, that can only handle one access at a time. Thus, since concurrently running threads may concurrently seek to invoke a method of an object, the object must be synchronized with only one thread at a time so that one thread owns and has exclusive use of the object. In other words, access to an object by a thread must be synchronized so that other threads do not have access to the object while it is synchronized with the thread.
In the past, various approaches have been used to synchronize an object with a thread. These include the use of synchronization constructs like mutexes, monitors, and semiphores. One approach that uses synchronization constructs, the run-time-allocation approach, is described in U.S. patent application No. 08/569805, entitled "OBJECT SYNCHRONIZATION MODULE AND METHOD WITH REDUCED MEMORY REQUIREMENTS", filed by Timothy G. Lindholm and Jonathan Payne on Dec. 8, 1995 (attorney docket no. A-62531).
In the run-time-allocation approach, synchronization constructs are allocated and de-allocated to objects as needed. For example, during run-time, a thread may invoke a method of an object that requires synchronization. A synchronization construct is allocated to the object if a synchronization construct has not already been allocated. When the thread exits the method that required synchronization of the thread with the object, and there are no other threads currently requiring synchronization with the object, the synchronization construct is deallocated from the object.
Synchronization constructs are stored in a data structure in global cache. Managing the allocation of these synchronization constructs to objects involves the use of other data structures which are also stored in global cache. A hash table links an object to its allocated synchronization construct. A free list contains entries identifying the synchronization constructs that are not allocated to any object.
Allocating a synchronization construct to an object entails operations which update the synchronization construct and the data structures used to manage allocation of synchronization constructs. These operations include, for example, updating the synchronization construct with information linking the synchronization construct to the object, creating an entry in the hash table linking the object to the synchronization construct, and removing the synchronization construct from the free list. Likewise, de-allocating a synchronization construct from an object includes operations such as removing an entry in the hash table linking the object to the synchronization construct, and adding the synchronization construct to the free list.
The operations involved in allocating and de-allocating synchronization constructs update data structures (i.e. the hash table, synchronization construct, and free list) in global cache. An update to a data structure in global cache requires a lock of a global data structure to prevent interference to and from other concurrently executing threads that may update the data structures. A lock of a global data structure is herein referred to as a global lock. A thread contending for a data structure globally locked by another thread is delayed until the other thread releases its global lock. Delays such as this one, which are caused by one thread contending for a data structure locked by another thread, are herein referred to as contention delays.
As threads executing in a computer system increase the number of operations performing updates on data structures in global cache, contention delays can often increase to undesirable levels. Thus frequently repeated allocations and de-allocations of synchronization constructs, which involve operations performing updates on data structures in global cache, can cause contention delays to reach undesirable levels.
Based on the foregoing, it clearly desirable to reduce contention delays caused by frequently repeated allocations and de-allocations of synchronization constructs.